Topology control is an important factor in the management/maintenance of mobile ad hoc networks (MANETs), where the underlying communication link topology may constantly change. A first requirement is finding a minimum connected subgraph of the network node topology to serve as a backbone for routing information. Various techniques have been proposed to propagate such routing topology information through a network. For instance, several routing protocols use multi-point relays (MPRs) to strategically propagate routing information in a controlled manner.
MPRs may be strategically selected to minimize the overhead of network node routing information while still covering the entire network. Network nodes that are not MPRs (i.e., ordinary nodes) transmit their routing information to all one hop neighbors only. MPR nodes then retransmit routing information heard by all one hop neighbors, thereby propagating the routing information to all MPR nodes throughout the connected network in time. The most notable protocol that employs MPRs is the Optimized Link State Routing (OLSR) protocol. The OLSR protocol may be implemented in MANETs.
Although MPRs may be utilized to propagate routing information, such relays are associated with a number of limitations. First, conventional MPRs used in routing protocols transmit link state information only. While link state information provides full topology of the network, it demands a large overhead in message complexity, which is directly proportional to the number of nodes and links in the network. Additionally, in dynamic mobile networks (e.g., MANETs), link state information may change before it can be propagated to all MPRs.
A further limitation associated with conventional use of MPRs is the election of MPRs using clustering techniques or algorithms whereby an elected MPR has an associated node group membership. With such techniques, if the MPR disappears from or loses connectivity with its group nodes, the associated nodes are left with no routing information until another MPR and group membership are formed. Therefore, such a configuration ties an entire group of nodes to an individual MPR, which may cause thrashing problems if the MPR disappears or loses connectivity from its node group members.
Therefore, it would be desirable to provide a method for propagating network node routing information that requires a limited amount of overhead and allows routing table updates to occur independent of node group membership.